Algoritmo di approssimazione

Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione. Gli algoritmi di approssimazione sono spesso associati a problemi NP-difficili; poiché è improbabile che ci possano essere algoritmi esatti efficienti in tempo polinomiale che risolvono problemi NP-difficili, ci si accontenta di soluzioni subottimali in tempo polinomiale. Diversamente dall'euristica, che di solito trova soluzioni ragionevolmente buone in tempi ragionevolmente veloci, in questo caso si vogliono soluzioni di qualità dimostrabile e tempi di esecuzione con limiti dimostrabili. Idealmente, l'approssimazione è ottimale fino a un piccolo fattore costante (ad esempio entro il 5% della soluzione ottimale). Gli algoritmi di approssimazione sono usati sempre di più per problemi dove gli algoritmi esatti in tempo polinomiale sono noti ma risultano troppo costosi a causa della dimensione dell'input.

Un esempio tipico di un algoritmo di approssimazione è quello per la copertura dei vertici nei grafi: trovare uno spigolo scoperto e aggiungere "entrambi" gli estremi alla copertura dei vertici, finché non ne rimane nessuno. È chiaro che la copertura risultante è al massimo due volte più grande di quella ottimale. Questo è un algoritmo di approssimazione a fattore costante con un fattore di 2.

I problemi NP-difficili variano grandemente nella loro approssimabilità; alcuni, come il problema dell'impacchettamento, può essere approssimato entro un qualsiasi fattore maggiore di 1 (tale famiglia di algoritmi di approssimazione è chiamata spesso schema di approssimazione in tempo polinomiale o PTAS). Altri sono impossibili da approssimare entro qualsiasi costante, o perfino fattore polinomiale, a meno che P = NP, come il problema della massima cricca.

I problemi NP-difficili spesso possono essere espressi come programmi interi (integer programs, IP) e risolti esattamente in tempo esponenziale. Molti algoritmi di approssimazione emergono dal rilassamento della programmazione lineare del programma intero.

Non tutti gli algoritmi di approssimazione sono adatti per tutte le applicazioni pratiche. Spesso usano risolutori IP/LP/semidefiniti, strutture dati complesse o tecniche algoritmiche sofisticate che conducono a problemi di difficile implementazione. Inoltre, alcuni algoritmi di approssimazione hanno tempi di esecuzione poco pratici anche se sono in tempo polinomiale, ad esempio O(n²⁰⁰⁰). Tuttavia lo studio di algoritmi anche molto costosi non è una ricerca completamente teorica, in quanto possono fornire preziose intuizioni. Un esempio classico è il PTAS iniziale per il TSP euclideo dovuto a Sanjeev Arora che aveva un tempo di esecuzione proibitivo; tuttavia entro un anno, Arora perfezionò le idee in un algoritmo in tempo lineare. Tali algoritmi sono validi anche in alcune applicazioni dove i tempi e il costo di esecuzione possono essere giustificati, ad es. biologia computazionale, ingegneria finanziaria, pianificazione dei trasporti e gestione degli inventari. In tali scenari, essi devono competere con le corrispondenti formulazioni IP dirette.

Un'altra limitazione dell'approccio è che esso si applica soltanto ai problemi di ottimizzazione e non ai problemi di decisione "puri" come la soddisfacibilità, sebbene sia spesso possibile concepire versionsi di ottimizzazione di tali problemi, come il problema della massima soddisfacibilità (Max SAT).

L'inapprossimabilità è stata un'area di ricerca fruttuosa nel campo della teoria della complessità computazionale fin dal risultato del 1990 di Feige, Goldwasser, Lovasz, Safra e Szegedy sull'inapprossimabilità dell'insieme indipendente. Dopo che Arora et al. dimostrarono il teorema PCP un anno dopo, si è mostrato che gli algoritmi di approssimazione elaborati nel 1974 da Johnson per il Max SAT, la copertura degli insiemi, l'insieme indipendente e la colorazione raggiungono tutti il rapporto ottimale di approssimazione, assumendo P != NP.